package MyList;

// 2、无头双向链表实现
public class LinkedList {

    ListNode phead;

    ListNode ptail;

    //头插法
    public void addFirst(int data){
        ListNode listNode=new ListNode(data);
        if (phead==null){
            phead=ptail=listNode;
        }else {
            listNode.next=phead;
            phead.front=listNode;
            phead=listNode;
        }
    }

    //尾插法
    public void addLast(int data){
        if (phead==null){
            addFirst(data);
            return;
        }
        ListNode listNode=new ListNode(data);
        listNode.front=ptail;
        ptail.next=listNode;
        ptail=listNode;
    }

    private boolean checkIndex(int index){
        int check=size();
        if(index<0||index>check){
            return false;
        }
        return true;
    }

    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if (!checkIndex(index)){
            throw new IndexOutOfException("位置非法！");
        }
        if (index==0){
            addFirst(data);
            return true;
        }
        if (index==size()){
            addLast(data);
            return true;
        }
        ListNode ps=phead;
        ListNode listNode=new ListNode(data);
        while (index--!=0){
            ps=ps.next;
        }
        listNode.front=ps.front;
        listNode.next=ps;
        ps.front.next=listNode;
        ps.front=listNode;
        return true;
    }

    //查找是否包含关键字key是否在链表当中
    public boolean contains(int key){
        ListNode ps=phead;
        while (ps!=null){
            if (ps.val==key)
                return true;
            ps=ps.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if (phead==null){
            System.out.println("链表为空！");
            return;
        }
        if (phead.val==key){
            phead=phead.next;
            if (phead!=null){
                phead.front=null;
            }else {
                ptail=null;
            }
            return;
        }
        if (ptail.val==key){
            ptail=ptail.front;
            if (ptail!=null){
                ptail.next=null;
            }else {
                phead=null;
            }
            return;
        }
        ListNode ps=phead;
        while(ps!=null){
            if (ps.val==key){
                ps.front.next=ps.next;
                ps.next.front=ps.front;
                return;
            }
            ps=ps.next;
        }
        System.out.println("未找到 "+key+" 节点！");
    }

    //删除所有值为key的节点
    public void removeAllKey(int key){
        if (phead==null){
            System.out.println("链表为空！");
            return;
        }
        ListNode pcur=phead;
        ListNode prev=phead.next;
        while (prev!=null){
            if(prev.val==key){
                while (prev!=null&&prev.val==key){
                    prev=prev.next;
                }
            }else {
                pcur.next=prev;
                prev.front=pcur;
                pcur=pcur.next;
                prev=prev.next;
            }
        }
        pcur.next=null;
        ptail=pcur;
        if (phead.val==key){
            phead=phead.next;
            if (phead!=null)
                phead.front=null;
        }
    }

    //得到链表的长度
    public int size(){
        ListNode ps=phead;
        int count=0;
        while(ps!=null){
            count++;
            ps=ps.next;
        }
        return  count;
    }

    public void display(){
        ListNode ps=phead;
        while(ps!=null){
            System.out.print(ps.val+" ");
            ps=ps.next;
        }
        System.out.println();
    }

    public void clear(){
        phead=null;
        ptail=null;
    }

}
